<TITLE>prob003: quasigroup existence</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob003: quasigroup existence</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.cs.york.ac.uk/~tw">
          <B>Toby Walsh</B></A> 
          <ADDRESS><a href="mailto:tw@cs.york.ac.uk">
          tw@cs.york.ac.uk</a></ADDRESS>
</TABLE>
with assistance from Kostas Stergiou and Mark Stickel. 
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Results </H3>
These problems have been a major success story for
automated reasoning and constraint satisfaction. 
Various open problems of interest to mathematicians
have been solved using a variety of different
computer programs including Slaney's constraint solver
FINDER, Zhang's Davis-Putnam procedure SATO, Stickel's LDPP procedure,
and the MGTP model generation program. 
Open problems solved include:
<CENTER>
<TABLE>
<TR> 
<TD> QG1 <TD> existence of idempotent QG1.12
<TR> 
<TD> QG2 <TD> existence of idempotent QG2.12, QG2.14-15
<TR> 
<TD> QG3 <TD> existence of idempotent QG3.12 
<TR> 
<TD> QG4 <TD> existence of idempotent QG4.12 
<TR> 
<TD> QG5 <TD> non-existence of QG5.10, QG5.14, and
of idempotent QG5.9-10 and QG5.12-16
<TR> 
<TD> QG6 <TD> existence of QG6.9 and QG6.17, non-existence of
QG6.7, QG6.10-11, QG6.14-15
<TR> 
<TR> 
<TD> QG7 <TD> non-existence of 
QG7.7-8, QG7.10-12 and QG7.14-16
</TABLE>
</CENTER>
<P>
Problems that remain open include:
<CENTER>
<TABLE>
<TR> 
<TD> QG2 <TD> idempotent QG2.10
<TR>
<TD> QG5 <TD> QG5.18, QG5.26, QG5.30, QG5.38, QG5.42, QG5.158,
<TR> 
<TD> <TD> 
and many of the idempotent cases starting at QG5.18
<TR>
<TD> QG6 <TD> QG6.20-21, QG6.24, 
QG6.41, QG6.44, 
QG6.48, QG6.53, 
QG6.60, QG6.69, 
<TR> 
<TD> <TD> 
QG6.77, QG6.93,
QG6.96, QG6.101,
QG6.161, QG6.164,
QG6.173
<TR> 
<TD> QG7 <TD> QG7.33
<TR>
</TABLE>
</CENTER>
<P>
<P>
For idempotent problems, the following table summarizes
some of these results where e=exists, n=no such quasigroup, 
and ?=open (some entries left blank as status not known
to problem proposer). 
<P>
<CENTER>
<TABLE>
<TR> 
<TD> order
<TD> 5
<TD> 6
<TD> 7
<TD> 8
<TD> 9
<TD> 10
<TD> 11
<TD> 12
<TD> 13
<TD> 14
<TD> 15
<TD> 16
<TD> 17
<TD> 18
<TD> 19
<TD> 20
<TR>
<TD> QG1 
<TD> e
<TD> n
<TD> e
<TD> e
<TD> e
<TD> e
<TD> e
<TD> e
<TD> e
<TD> e
<TD> e
<TD> e
<TD> e
<TD> e
<TD> e
<TD> e
<TR>
<TD> QG2
<TD> e
<TD> n
<TD> e
<TD> e
<TD> e
<TD> ?
<TD> e
<TD> e
<TD> e
<TD> e
<TD> e
<TD> e
<TD> e
<TD> e
<TD> e
<TD> e
<TR>
<TD> QG3
<TD> e
<TD> n
<TD> n
<TD> e
<TD> e
<TD> n
<TD> n
<TD> e
<TD> e
<TD> n
<TD> n
<TD> e
<TD> e
<TD> n
<TD> n
<TD> e
<TR>
<TD> QG4
<TD> n
<TD> n
<TD> n
<TD> e
<TD> e
<TD> n
<TD> n
<TD> e
<TD> e
<TD> n
<TD> n
<TD> e
<TD> e
<TD> n
<TD> n
<TD> e
<TR>
<TD> QG5
<TD> e
<TD> n
<TD> e
<TD> e
<TD> n
<TD> n
<TD> e
<TD> n
<TD> n
<TD> n
<TD> n
<TD> n
<TD> e
<TD> ?
<TD> e
<TD> ?
<TR>
<TD> QG6
<TD> n
<TD> n
<TD> n
<TD> e
<TD> e
<TD> n
<TD> n
<TD> n
<TD> e
<TD> n
<TD> n
<TD> e
<TD> e
<TD> n
<TD> n
<TD> ?
<TR>
<TD> QG7
<TD> e
<TD> n
<TD> n
<TD> n
<TD> e
<TD> n
<TD> n
<TD> n
<TD> e
<TD> n
<TD> n
<TD> 
<TD> e
<TD> 
<TD> 
<TD> 
<TR>

</TABLE>
</CENTER>





<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.


